package com.liuyfly.leetcode.questions;

import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

/**
 * @author liuyangfang at 2022-09-04 15:45
 */
@Slf4j
public class Question0020 {
    static char left1 = '(', right1 = ')';
    static char left2 = '[', right2 = ']';
    static char left3 = '{', right3 = '}';

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
     * <p>
     * 有效字符串需满足：<ul>
     * <li>左括号必须用相同类型的右括号闭合。</li>
     * <li>左括号必须以正确的顺序闭合。</li>
     * <li>每个右括号都有一个对应的相同类型的左括号。</li>
     * </ul>
     * <p><br/>
     * <br/>
     * 链接：https://leetcode.cn/problems/valid-parentheses
     */
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            if (ch == left1 || ch == left2 || ch == left3) {
                stack.push(ch);
                continue;
            }
            if (stack.isEmpty()) {
                return false;
            }
            char popChar = stack.pop();
            if (!isMatch(popChar, ch)) {
                return false;
            }
        }
        return stack.isEmpty();
    }

    public static boolean isMatch(char left, char right) {
        if (left == left1 && right == right1) {
            return true;
        }
        if (left == left2 && right == right2) {
            return true;
        }
        if (left == left3 && right == right3) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
//        String str = "()";
//        String str = "()[]{}";
//        String str = "()[]}";
        String str = "(";
        log.info("string \"{}\" is isValid:{}", str, isValid(str));
    }
}
